package com.mgq.algorithm;

import java.util.List;

/**
 * @author MaGuangQi
 * @description: 反转一个链表
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 * <p>
 *  
 * <p>
 * 示例: 输入:1->2->3->4->5->NULL
 * <p>
 *      输出: 5->4->3->2->1->NULL
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020-06-10 23:08
 **/
public class ReverseList {
    /**
    *解法一: 使用双指针,定义2个指定,第一个指针pre是前驱节点
     * 第二个是当前节点cur
     * 一开始pre指向空,cur指向当前
     * 将当前节点的next指向临时节点保存
     * 然后将当前节点的next指向pre  相当于 1->null
     * 然后再pre和cur向后移动一位
     * 即 cur=tmp;
     *   pre=cur;
     *
    */
    public ListNode reverseList(ListNode head) {
        ListNode tmp = null;
        ListNode pre=null;
        ListNode cur=head;
        while (cur != null) {
            //将下一个节点临时保存
            tmp=cur.next;
            //将当前节点指向前一个节点
            //tmp得保存下一个节点,否则此处就覆盖了.
            cur.next=pre;
            //2个指针向后移1位
            pre=cur;
            cur=tmp;
        }

        return pre;
    }
    /**
    *解法二:使用递归
     ** 示例: 输入:1->2->3->4->5->NULL
     *  输出: 5->4->3->2->1->NULL
     *
     *  f(5)=5*f(4)
     *  f(4)=5*4*f(3)
     *  f(3)=5*4*3*f(2)
     *  f(2)=5*4*3*2*f(1)
     *  f(1)=5*4*3*2*11
     *
     *  第一次 5->4
     *  第二次 5->4->3
     *  第三次 5->4->3->2
    */

    public ListNode reverseList2(ListNode head) {
        //终止递归的条件是 head=null || head.next=null
        //假设有5个数,最后进入if时,此时if里面的head=5; 想想f(5)=5*f(4)
        if (head == null || head.next == null) {
            return head;
        }
        //也就是说head.next是个值, 最后进if里面时是5.最后一个递归完成,开始往外
        //此时head就变成4了. cur是最后一次的返回值就是5
        ListNode cur = reverseList2(head.next);
            //head.next.next=head,可以分开看,首先 head.next是个值ListNode
            //然后ListNode.next=head 是赋值操作
            //也就是说 最后一次 head.next=5
            //5.next=head, 就是5.next=4, 把4的值赋值给5.next.不就是5指向4吗
            head.next.next=head;
            //此时head.next还在指向5, 也就是说既是5->4,同时4->5.所以将head.next指向null.避免闭环
            head.next=null;
            return cur;
    }



    private class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
}
